package LearnDataStructure.c_树结构.无序树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 21:31
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.无序树
 */
/*
存在以下字母串：AGDCCDDDGFBBFFGGDDDGGGEFFDDCCCDDDFGAAA现在需要对该串进行huffman编码，
那么字母F对应bit值（二进制格式为）101

AAAABBCCCCCDDDDDDDDDDDDEFFFFFFGGGGGGGG
A-4 B-2 C-5 D-12 E-1 F-6 G-8
选择最小的两个节点作为子节点，相加形成一个虚的父节点，
删除子节点，将父节点添加到列表中递归上一步
1
    （3）
2       （7）
     4        （15）
         8
                        （38）
     5
        （11）
     6        （23）
         12
 */
public class HuffmanTree {

    public static void main(String[] args) {
        HuffmanTree test = new HuffmanTree();
        test.useHuffman();
    }

    public void useHuffman() {
        String str = "AGDCCDDDGFBBFFGGDDDGGGEFFDDCCCDDDFGAAA";
        NodeHuffman root = operateHuffman(str);
        String result = findHuffmanCode(root, 'F');
        String substring = result.substring(0, result.length() - 1);
        System.out.println(substring);
    }

    public String findHuffmanCode(NodeHuffman node, char tagret) {
        if (node.left == null && node.right == null) {
            if (node.word == tagret) {
                return "@";
            } else {
                return null;
            }
        }
        String leftRes = findHuffmanCode(node.left, tagret);
        String rightRes = findHuffmanCode(node.right, tagret);
        if (leftRes == null && rightRes != null) {
            return "1"+rightRes;
        } else if (leftRes != null && rightRes == null) {
            return "0"+leftRes;
        } else {
            return null;
        }
    }

    public NodeHuffman operateHuffman(String source) {
        char[] sourceChars = source.toCharArray();
        Arrays.sort(sourceChars);
        int[] counts = new int[26];
        char temp = sourceChars[0];
        for (int i = 0; i < sourceChars.length; i++) {
            if (sourceChars[i] == temp) {
                counts[temp - 'A']++;
            } else {
                temp = sourceChars[i];
                counts[temp - 'A']++;
            }
        }

        List<NodeHuffman> nodes = new ArrayList<NodeHuffman>();
        for (int i = 0; i < 26; i++) {
            if (counts[i] != 0) {
                nodes.add(new NodeHuffman((char) ('A' + i), counts[i]));
            }
        }
        nodes.sort(new Comparator<NodeHuffman>() {
            @Override
            public int compare(NodeHuffman thisNode, NodeHuffman otherNode) {
                return thisNode.value - otherNode.value;
            }
        });

        List<NodeHuffman> trees = new ArrayList<>();
        trees.add(nodes.get(0));
        for (int i = 1; i < nodes.size(); i++) {
            int j = trees.size() - 1;
             while (j >= 0) {
                 NodeHuffman treeNode = trees.get(j);
                 NodeHuffman outNode = nodes.get(i);
                 if (treeNode.value < outNode.value) {
                     NodeHuffman parent = new NodeHuffman(treeNode.value + outNode.value, treeNode, outNode, true);
                     treeNode.parent = parent;
                     treeNode.isLeft = true;
                     outNode.parent = parent;
                     outNode.isLeft = false;
                     trees.set(j,parent);
                     break;
                 } else {
                     j--;
                 }
             }
             if (j < 0) {
                 trees.add(nodes.get(i));
             }
        }

        trees.sort(new Comparator<NodeHuffman>() {
            @Override
            public int compare(NodeHuffman thisNode, NodeHuffman otherNode) {
                return thisNode.value - otherNode.value;
            }
        });
        if (trees.size() == 1) {
            return trees.get(0);
        }
        while (trees.size() > 1) {
            NodeHuffman currentNode = trees.get(0);
            NodeHuffman nextNode = trees.get(1);
            NodeHuffman parent = new NodeHuffman(currentNode.value + nextNode.value, currentNode, nextNode, true);
            currentNode.parent = parent;
            currentNode.isLeft = true;
            nextNode.parent = parent;
            nextNode.isLeft = false;

            trees.remove(0);//list的remove会自动进行元素移动
            trees.remove(0);//所以删除两次首元素就完成了删除原list的索引0，1的元素
            trees.add(parent);
            trees.sort(new Comparator<NodeHuffman>() {
                @Override
                public int compare(NodeHuffman thisNode, NodeHuffman otherNode) {
                    return thisNode.value - otherNode.value;
                }
            });
        }

        return trees.get(0);
    }

    class NodeHuffman implements Comparable<NodeHuffman> {
        public char word;
        public int value;
        public NodeHuffman parent;
        public NodeHuffman left;
        public NodeHuffman right;
        public boolean isLeft = true;

        public NodeHuffman(char word, int value) {
            this.word = word;
            this.value = value;
        }

        public NodeHuffman(int value, NodeHuffman left, NodeHuffman right, boolean isLeft) {
            this.value = value;
            this.left = left;
            this.right = right;
            this.isLeft = isLeft;
        }

        public void setParent(NodeHuffman parent) {
            this.parent = parent;
        }

        @Override
        public int compareTo(NodeHuffman other) {//从小到大排序
            int res = this.value - other.value;
            return res;
        }
    }

}
